# 旋转链表： https://leetcode-cn.com/problems/rotate-list/submissions/
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        """
            这道题最基本的想法是， 快慢指针求出来 第倒数k位置，然后减下来拼接到头部即可。 但是 k 值可能大于链表长度，所以
            1. 计划先求链表的长度
            2. k 与 链表长度 取模求
            3. 再找到位置，截断加到头部
        """
        # 注意1： 链表长度
        if not head or not head.next:
            return head

        lenLinked = 1
        cur = head
        # 计算链表长度
        while cur.next:
            cur = cur.next
            lenLinked += 1
        
        # 注意2： 如果 k == 0 或者 k 为 链表长度的倍数，无需反转，反转后也是原来长度（最主要是我这样的拆分拼接，处理不了这两点）
        if k == 0 or k % lenLinked == 0:
            return head

        k = k % lenLinked
        preLow = fast = low = head
        for i in range(k-1):
            fast = fast.next
        # 找到k位置
        while fast.next:
            fast = fast.next
            preLow = low
            low = low.next

        # 拿出来拼接到前面
        preLow.next = None
        fast.next = head
        head = low

        return head